package Algorithm.PrefixSum;
// https://leetcode-cn.com/problems/longest-absolute-file-path/
public class Leetcode388_文件的最长绝对路径 {
    /**
     * 当前文件的长度 = 文件长度 + 最近邻上一层的长度
     * 对于每一个文件来说，需要的只是最近邻上一层的长度，使用一个数组来保存
     */
    class Solution {
        public int lengthLongestPath(String input) {
            String[] arrays = input.split("\n");
            int n = arrays.length;
            if (n < 2){
                if (input.contains(".")){
                    return input.length();
                }else{
                    return 0;
                }
            }

            // 保存不同层级的字符长度
            int[] d = new int[n];
            int max = 0;

            for (int i = 0; i < n; i++){
                // 判断该文件的层级
                int num = count(arrays[i], "\t");
                int beforeNum = num - 1 ;

                if (beforeNum >= 0){
                    // 计算第 num 层的长度，由上一层和当前层的长度相加得到。
                    // 对于后面的文件来说，第i层是他们最近邻的上一层，尽管现在的 d[nums]不是最大值
                    d[num] = d[beforeNum] + arrays[i].length() - num * 1;
                }else{
                    d[num] = arrays[i].length() - num * 1;
                }

                // 如果是文件，更新最长长度
                if (arrays[i].contains(".")){
                    max = Math.max(max, d[num] + num);
                }
            }

            return max;
        }

        public int count(String input, String sub){
            int num = 0;
            while(input.contains(sub)){
                input = input.substring(input.indexOf(sub) + sub.length(), input.length());
                num ++;
            }
            return num;
        }
    }
}
